Mapa gestosci
Limit pamięci: 32 MB
Dane są:
- liczby naturalne ,
- - tabelka wypełniona
liczbami ze zbioru ;
kolumny i wiersze tabelki są ponumerowane od 1 do ;
liczbę znajdującą sie w -tej kolumnie i -tym wierszu
tabelki oznaczamy przez .
Jeśli
i
są dwoma miejscami w tabelce
, to
odległością między nimi nazywamy liczbę
.
Należy obliczyć tabelkę , (do elementów tej tabelki
odwołujemy się tak samo, jak do elementów tabelki )
taką, że jest sumą wszystkich liczb z tabelki leżących
w odległości co najwyżej od .
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia liczby oraz
tabelkę ,
- obliczy tabelkę ,
- wypisze ją na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie dodatnie
liczby całkowite oddzielone pojedynczą spacją: i ,
gdzie .
W kolejnych wierszach znajduje się opis tabelki .
Każdy z tych wierszy zawiera liczb ze zbioru ,
pooddzielanych pojedynczymi odstępami, -ta liczba zapisana w -szym
wierszu to .
Wyjście
Standardowe wyjście powinno zawierać dokładnie wierszy,
w -tym wierszu powinny być zapisane kolejno wartości
pooddzielane pojedynczymi odstępami.
Przykład
Dla danych wejściowych:
5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
poprawną odpowiedzią jest:
3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2
Autor zadania: Tomasz Śmigielski.